Processors often use a cache to improve performance and decrease system costs. Caches temporarily store recently accessed information (blocks of instructions or data) in a small memory that is faster to access than a larger main memory. Caches are effective because a block that has been accessed once is likely to be accessed soon again or is often near a recently accessed block. Thus, as a task executes, the working set of a task (the instructions and data currently required for the task) is stored in the cache in the event that the information may be accessed again. A cache typically maps multiple blocks of information from the main memory into one place in a cache, typically referred to as a “set.” A “block” refers to the minimum unit of information that can be present in a cache and a “frame” is the place in a cache where a single block may be stored. In a set associative cache, multiple frames are grouped into sets. For example, as two-way set associative cache has two frames in each set.
Index bits in the address of a block of main memory select a set to hold the block in the cache. The index bits thus associate (map) a block to a cache set. Any of the frames in the set may hold a block that maps to the set. When a new block is stored in a set, it is typically stored in the least recently accessed frame of the set. A block that currently resides in the frame (if any) is evicted from the cache. A cache directory is typically used to determine if a given block is in the cache. The directory is often a table of entries, one entry for each set in the cache. An entry contains one field for each frame in its associated set. To determine if a block is in the cache, the corresponding index bits are used to select a directory entry. If a given block is in the cache, the address of the block is in one of the entry's frame fields.
The index bits specify the set that holds the block in the cache. Thus, all blocks with the same index map to the same set. If there are not enough frames in a set to store all the blocks that map to the set that are currently in use by a program, one or more frames must be evicted prematurely (i.e., before temporally local accesses to them have completed), thereby increasing cache misses. This phenomenon is referred to as “thrashing” and can significantly decrease cache performance. A need therefore exists for an adaptive mechanism to decrease cache trashing in a cache memory device. A further need exists for a mechanism for extending a cache set when such thrashing occurs.